package com.mdnote.structure.recuirsion;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/24
 * @description 迷宫问题
 */
public class MazeQuestion {

    private int[][] maze;

    public MazeQuestion(int width, int height) {
        this.maze = new int[width][height];
    }

    // 设置障碍
    public void setHinder(int x, int y) {
        this.maze[x][y] = 1;
    }

    public boolean gp(int fromX, int fromY, int toX, int toY) {

        // TTerminate
        if (fromX == toX && fromY == toY) {
            return true;
        }

        // 1 墙壁  2 走过  3 死路
        // 没有做过
        if (this.maze[fromX][fromY] == 0) {
            // 假定走过了能走通
            this.maze[fromX][fromY] = 2;
            // 向下走
            if (gp(fromX + 1, fromY, toX, toY)) {
                return true;
            }
            // 向右走
            if (gp(fromX, fromY + 1, toX, toY)) {
                return true;
            }
            // 向上走
            if (gp(fromX - 1, fromY, toX, toY)) {
                return true;
            }
            // 向左走
            if (gp(fromX, fromY - 1, toX, toY)) {
                return true;
            }
        } else {
            // 做过了或者是死路
            this.maze[fromX][fromY] = 3;
        }
        return false;
    }

    public void show() {
        for (int i = 0; i < this.maze.length; i++) {
            for (int j = 0; j < this.maze[0].length; j++) {
                System.out.print(this.maze[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        MazeQuestion mazeQuestion = new MazeQuestion(8, 8);
        // 设置墙壁
        for (int i = 0; i < 8; i++) {
            mazeQuestion.setHinder(i, 0);
            mazeQuestion.setHinder(i, 7);
        }
        for (int i = 0; i < 8; i++) {
            mazeQuestion.setHinder(0, i);
            mazeQuestion.setHinder(7, i);
        }
        mazeQuestion.setHinder(2, 1);
        mazeQuestion.setHinder(2, 2);
        mazeQuestion.setHinder(3, 3);

        mazeQuestion.show();

        mazeQuestion.gp(1,1,6,5);

        System.out.println("-------------------------");
        mazeQuestion.show();
    }
}
